package task2;

public class MultiThreadMergeSorter {

	private volatile Integer[] sortedArray;

	public Integer[] doMergeSort(Integer[] inputArray) {
		sortedArray = new Integer[inputArray.length];

		for (int i = 0; i < sortedArray.length; i++) {
			sortedArray[i] = inputArray[i];
		}

		Thread mst = new Thread(new mergeSortThread(sortedArray,
				0, inputArray.length - 1));

		mst.start();

		try {
			mst.join();
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		return sortedArray;
	}

	class mergeSortThread implements Runnable {

		Integer[] inputArray;
		int start;
		int end;

		mergeSortThread(Integer[] inputArray, int start, int end) {
			this.inputArray = inputArray;
			this.start = start;
			this.end = end;
		}

		public void run() {

			if (start == end) {
				return;
			}

			int mid = ((end - start + 1) / 2) - 1;

			Thread mst1 = new Thread(new mergeSortThread(inputArray,
					start, start + mid));

			Thread mst2 = new Thread(new mergeSortThread(inputArray,
					start + mid + 1, end));

			mst1.start();
			mst2.start();

			try {
				mst1.join();
				mst2.join();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}

			Integer[] aux = new Integer[end - start + 1];
			for (int i = start, j = 0; i <= end; i++, j++) {
				aux[j] = inputArray[i];
			}

			for (int i = 0, j = mid + 1, k = start; k <= end; k++) {
				if (i > mid) {
					inputArray[k] = aux[j++];
				} else if (j > aux.length - 1) {
					inputArray[k] = aux[i++];
				} else if (aux[i].compareTo(aux[j]) < 0) {
					inputArray[k] = aux[i++];
				} else {
					inputArray[k] = aux[j++];
				}
			}
		}
	}
}